package LeetCodeHot100TopInterview;

public class Q114_TreeToSingleList {

    //二叉树转单链表
    //题目类似剑指offer - Q36
    //此题为展开为单链表 要求按照前序遍历 往右下串
    //具体解决方案:
    //https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/
    public void flatten(TreeNode root) {

        //前序遍历 ==> 根  | 左 | 右
        //算法流程 ... 左子树最右节点（前驱节点） | 根 | 右子树
        //迭代 ... 右子树接到前驱节点上  再接到根节点的右子树上 完成前序顺序调整

        TreeNode cur = root;
        TreeNode left = null; //根节点的左节点
        TreeNode tmp = null; //根节点的前驱节点（左子树最右节点）
        while (cur != null){
            if (cur.left != null){
                //每个小迭代过程
                tmp = cur.left;
                //找到最右节点 前驱节点
                while (tmp.right != null){
                    tmp = tmp.right;
                }
                tmp.right = cur.right;
                //断线重连
                left = cur.left;
                cur.left = null;
                cur.right = left;
            }
            cur = cur.right;
        }
    }
}
